package com.zjsru.oneDay202210;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: CookLee
 * @Date: 2022/10/30
 *
 * 字母大小写全排列
 *
 * 输入：s = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 *
 * 输入: s = "3z4"
 * 输出: ["3z4","3Z4"]
 */
public class LetterCasePermutation {
    
    char[] cs;
    
    List<String> ans = new ArrayList<>();
    
    /**
     * BFS
     * 其中 n 固定为具体方案的长度（即原字符串长度），而 idx 和 cur 分别为当前处理到哪一个 s[idx]，而 cur 则是当前具体方案。
     *
     */
    public List<String> letterCasePermutation(String s) {
        cs = s.toCharArray();
        dfs(0, s.length(), new char[s.length()]);
        return ans;
    }
    
    private void dfs(int idx, int n, char[] cur) {
        if (idx == n) {
            ans.add(String.valueOf(cur));
            return;
        }
        cur[idx] = cs[idx];
        dfs(idx + 1, n, cur);
        if (Character.isLetter(cs[idx])) {
            //当为字母是转化为大写
            cur[idx] = (char) (cs[idx] ^ 32);
            dfs(idx + 1, n, cur);
        }
    }
    
    public static void main(String[] args) {
        LetterCasePermutation letterCasePermutation = new LetterCasePermutation();
        String s = "3z4";
        System.out.println(letterCasePermutation.letterCasePermutation(s));
    }
}
